//
// Created by zx208 on 2024/11/2.
//
// 这里是利用自定义的栈来进行非递归遍历二叉树

#include "LinkedStack_BinaryTree.h"

Status Init_ST(LinkedStack_BT *S){
    *S = NULL;
    return OK;
}

Status Push_ST(LinkedStack_BT *S, BiNode e){
    LinkedStack_BT p = (LinkedStack_BT) malloc(sizeof( StackNode_BT));
    p->data = e;
    p->next = *S;
    *S = p;
    return OK;
}

Status Pop_ST(LinkedStack_BT *S, BiNode *e){
    LinkedStack_BT pfree = *S;
    *e = (*S)->data;
    *S = (*S)->next;
    free(pfree);
    return OK;
}

BiNode GetTop_ST(LinkedStack_BT *S) {
    if (*S) return (*S)->data;
    else exit(OVERFLOW);
}

Status IsEmpty_ST(LinkedStack_BT *S){
    if (!(*S)) return TRUE;
    else return FALSE;
}

// 使用先序遍历创建二叉树
void Create_BiTree_Pre(BiTree *T){
    char e;
    scanf(" %c", &e);
    if(e == '#') *T = NULL;
    else {
        *T = (BiTree) malloc(sizeof(  BiNode));
        (*T)->data = e;
        Create_BiTree_Pre(&(*T)->lchild);
        Create_BiTree_Pre(&(*T)->rchild);
    }
}

// 先序遍历
void PreOrder_unrec(BiTree T){
    LinkedStack_BT S;
    Init_ST(&S);
    BiTree p = T;
    while(p || !IsEmpty_ST(&S)){
        if(p){
            printf("%c ", p->data);
            Push_ST(&S, *p);
            p = p->lchild;
        } else{
            BiTree tmp = (BiTree) malloc(sizeof( BiNode));
            Pop_ST(&S, tmp);
            p = tmp->rchild;
        }
    }
}

// 中序遍历
void InOrder_unrec(BiTree T){
    LinkedStack_BT S;
    Init_ST(&S);
    BiTree p = T;
    while(p || !IsEmpty_ST(&S)){
        if(p){
            Push_ST(&S, *p);
            p = p->lchild;
        } else{
            // 在这里需要自己再创建一个tmp来存储pop出来的tree node
            BiTree tmp = (BiTree) malloc(sizeof( BiNode));
            Pop_ST(&S, tmp);
            printf("%c ", tmp->data);
            p = tmp->rchild;
        }
    }
}

// TODO 后序遍历
void PostOrder_unrec(BiTree T){
    LinkedStack_BT S;
    Init_ST(&S);
    BiTree p = T, r = NULL;
    while(p || !IsEmpty_ST(&S)){
        if(p){
            Push_ST(&S, *p);
            p = p->lchild;
        } else{
            // 在这里如果申请新地址的话 会发现 tmp->rchild != r 会出错
            // 所以在这里我们需要重新构思
            BiTree tmp = (BiTree) malloc(sizeof( BiNode));
            *tmp = GetTop_ST(&S);
            if(tmp->rchild && tmp->rchild != r) p = tmp->rchild;
            else{
                Pop_ST(&S, tmp);
                printf("%c ", tmp->data);
                r = tmp;
                p = NULL;
            }
        }
    }
}


int main(void){
    BiTree T = NULL;
    Create_BiTree_Pre(&T);
    PreOrder_unrec(T);
    printf("\n");
    InOrder_unrec(T);
    printf("\n");
    PostOrder_unrec(T);
    return 0;
}

// CDNK##J##BZ###FL##M##